Data broadcast is a fundamental operation in wireless sensor networks (WSNs). The existence of wireless interference makes\r\nit nontrivial to design a minimum-latency broadcast scheme, which is known to be NP-hard. Existing works all assume strict\r\ntime synchronization and provide centralized TDMA scheduling algorithms. However, WSNs in practice are more likely to be\r\ndistributed asynchronous systems. In this paper, we investigate the problem of data broadcast with minimum latency for distributed\r\nasynchronous WSNs. To this end, we propose a Distributed Asynchronous Broadcast (DAB) algorithm which crucially leverages\r\nan elaborately optimized carrier-sensing range together with collision-backoff schemes to coordinate the transmissions among\r\nthe nodes on a predetermined broadcast backbone. Theoretical analysis shows that DAB is order-optimal and achieves constant\r\nfactor approximation to the optimal delay. We then conduct extensive simulations to evaluate the practical capability of DAB in\r\nasynchronousWSNs and the results corroborate our theoretical analysis.
Loading....